home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / source.exe / POSIX / FIND / FTS.C < prev    next >
C/C++ Source or Header  |  1992-10-29  |  25KB  |  924 lines
  1.  /* Copyright (c) 1990 The Regents of the University of California.
  2.  * All rights reserved.
  3.  *
  4.  * Redistribution and use in source and binary forms, with or without
  5.  * modification, are permitted provided that the following conditions
  6.  * are met:
  7.  * 1. Redistributions of source code must retain the above copyright
  8.  *    notice, this list of conditions and the following disclaimer.
  9.  * 2. Redistributions in binary form must reproduce the above copyright
  10.  *    notice, this list of conditions and the following disclaimer in the
  11.  *    documentation and/or other materials provided with the distribution.
  12.  * 3. All advertising materials mentioning features or use of this software
  13.  *    must display the following acknowledgement:
  14.  *    This product includes software developed by the University of
  15.  *    California, Berkeley and its contributors.
  16.  * 4. Neither the name of the University nor the names of its contributors
  17.  *    may be used to endorse or promote products derived from this software
  18.  *    without specific prior written permission.
  19.  *
  20.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30.  * SUCH DAMAGE.
  31.  */
  32.  
  33. #ifdef DF_POSIX
  34. #include <df/types.h>
  35. #endif
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)fts.c    5.19 (Berkeley) 5/9/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/cdefs.h>
  42. #ifdef _POSIX_SOURCE    /* DF_DSC: POSIX does not need this, as */
  43. #else                   /* only MAXPATHLEN was found there,     */
  44. # include <sys/param.h> /* and it wants machine directory stuff */
  45. #endif
  46. #include <sys/stat.h>
  47. #include <fcntl.h>
  48. #include <dirent.h>
  49. #include <errno.h>
  50. #include "fts.h"
  51. #include <stdlib.h>
  52. #include <string.h>
  53. #include <unistd.h>
  54.  
  55. static FTSENT *fts_alloc __P((FTS *, char *, register int));
  56. static FTSENT *fts_build __P((register FTS *, int));
  57. static FTSENT *fts_sort __P((FTS *, FTSENT *, register int));
  58. static void fts_load __P((FTS *, register FTSENT *));
  59. static void fts_lfree __P((register FTSENT *));
  60. static u_short fts_stat __P((FTS *, register FTSENT *, int));
  61. static char *fts_path __P((FTS *, int));
  62.  
  63. #define    ISSET(opt)    (sp->fts_options & opt)
  64. #define    SET(opt)    (sp->fts_options |= opt)
  65.  
  66. #define    CHDIR(sp, path)    (!ISSET(FTS_NOCHDIR) && chdir(path))
  67.  
  68. #ifdef _POSIX_SOURCE /* DF_DSC: fchdir not in POSIX */
  69. #else
  70. #define    FCHDIR(sp, fd)    (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  71. #endif
  72.  
  73. /* fts_build flags */
  74. #define    BCHILD        1        /* from fts_children */
  75. #define    BREAD        2        /* from fts_read */
  76.  
  77. FTS *
  78. #if __STDC__
  79. fts_open (char * const *argv, register int options, int (*compar)(const FTSENT *, const FTSENT *))
  80. #else
  81. fts_open(argv, options, compar)
  82.     char * const *argv;
  83.     register int options;
  84.     int (*compar)();
  85. #endif
  86. {
  87.     register FTS *sp;
  88.     register FTSENT *p, *root;
  89.     register int nitems, maxlen;
  90.     FTSENT *parent, *tmp;
  91.     int len;
  92.  
  93.     /* Allocate/initialize the stream */
  94.     if (!(sp = (FTS *)malloc((u_int)sizeof(FTS))))
  95.         return(NULL);
  96.     bzero(sp, sizeof(FTS));
  97.     sp->fts_compar = compar;
  98.     sp->fts_options = options;
  99.  
  100.     /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
  101.     if (ISSET(FTS_LOGICAL))
  102.         SET(FTS_NOCHDIR);
  103.  
  104. #if DF_POSIX
  105. /* DF_MSC: force NOCHDIR because chdir("..") fails for large trees */
  106.     SET(FTS_NOCHDIR);
  107. #endif
  108.  
  109.     /* Allocate/initialize root's parent. */
  110.     if (!(parent = fts_alloc(sp, "", 0)))
  111.         goto mem1;
  112.     parent->fts_level = FTS_ROOTPARENTLEVEL;
  113.  
  114.     /* Allocate/initialize root(s). */
  115.     maxlen = -1;
  116.     for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
  117.         if (!(len = strlen(*argv))) {
  118.             errno = ENOENT;
  119.             goto mem2;
  120.         }
  121.         if (maxlen < len)
  122.             maxlen = len;
  123.         p = fts_alloc(sp, *argv, len);
  124.         p->fts_level = FTS_ROOTLEVEL;
  125.         p->fts_parent = parent;
  126.         /*
  127.          * If comparison routine supplied, traverse in sorted
  128.          * order; otherwise traverse in the order specified.
  129.          */
  130.         if (compar) {
  131.             p->fts_link = root;
  132.             root = p;
  133.             p->fts_accpath = p->fts_name;
  134.             if (!(options & FTS_NOSTAT))
  135.                 p->fts_info = fts_stat(sp, p, 0);
  136.         } else {
  137.             p->fts_link = NULL;
  138.             if (!root)
  139.                 tmp = root = p;
  140.             else {
  141.                 tmp->fts_link = p;
  142.                 tmp = p;
  143.             }
  144.         }
  145.     }
  146.     if (compar && nitems > 1)
  147.         root = fts_sort(sp, root, nitems);
  148.  
  149.     /*
  150.      * Allocate a dummy pointer and make fts_read think that we've just
  151.      * finished the node before the root(s); set p->fts_info to FTS_NS
  152.      * so that everything about the "current" node is ignored.
  153.      */
  154.     if (!(sp->fts_cur = fts_alloc(sp, "", 0)))
  155.         goto mem2;
  156.     sp->fts_cur->fts_link = root;
  157.     sp->fts_cur->fts_info = FTS_NS;
  158.  
  159.     /* Start out with at least 1K+ of path space. */
  160. #ifdef _POSIX_SOURCE /* DF_DSC: POSIX defines PATH_MAX */
  161.     if (!fts_path(sp, __max(maxlen, PATH_MAX)))
  162.             goto mem3;
  163.     if ((sp->fts_rpath = malloc(PATH_MAX)) == NULL)
  164.             goto mem4;
  165. #else
  166.     if (!fts_path(sp, MAX(maxlen, MAXPATHLEN)))
  167.         goto mem3;
  168. #endif
  169.  
  170.     /*
  171.      * If using chdir(2), grab a file descriptor pointing to dot to insure
  172.      * that we can get back here; this could be avoided for some paths,
  173.      * but almost certainly not worth the effort.  Slashes, symbolic links,
  174.      * and ".." are all fairly nasty problems.  Note, if we can't get the
  175.      * descriptor we run anyway, just more slowly.
  176.      */
  177. #ifdef _POSIX_SOURCE /* DF_DSC: use getpwd because no fchdir for later */
  178.     if (!ISSET(FTS_NOCHDIR) && (getcwd(sp->fts_rpath, PATH_MAX)) == NULL)
  179. #else
  180.     if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
  181. #endif
  182.         SET(FTS_NOCHDIR);
  183.  
  184.     return(sp);
  185. #ifdef _POSIX_SOURCE /* DF_DSC */
  186. mem4:   free(sp->fts_path);
  187. #endif
  188. mem3:    free(sp->fts_cur);
  189. mem2:    fts_lfree(root);
  190.     free(parent);
  191. mem1:    free(sp);
  192.     return(NULL);
  193. }
  194.  
  195. static void
  196. #if __STDC__
  197. fts_load (FTS *sp, register FTSENT *p)
  198. #else
  199. fts_load(sp, p)
  200.     FTS *sp;
  201.     register FTSENT *p;
  202. #endif
  203. {
  204.     register int len;
  205.     register char *cp;
  206.  
  207.     /*
  208.      * Load the stream structure for the next traversal.  Since we don't
  209.      * actually enter the directory until after the preorder visit, set
  210.      * the fts_accpath field specially so the chdir gets done to the right
  211.      * place and the user can access the first node.
  212.      */
  213.     len = p->fts_pathlen = p->fts_namelen;
  214.     bcopy(p->fts_name, sp->fts_path, len + 1);
  215.     if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
  216.         len = strlen(++cp);
  217.         bcopy(cp, p->fts_name, len + 1);
  218.         p->fts_namelen = len;
  219.     }
  220.     p->fts_accpath = p->fts_path = sp->fts_path;
  221.  
  222.     p->fts_info = fts_stat(sp, p, 0);
  223.     sp->rdev = p->fts_statb.st_dev;
  224. }
  225.  
  226. int
  227. #if __STDC__
  228. fts_close (FTS *sp)
  229. #else
  230. fts_close(sp)
  231.     FTS *sp;
  232. #endif
  233. {
  234.     register FTSENT *freep, *p;
  235.     int saved_errno;
  236.  
  237.     if (sp->fts_cur) {
  238.         /*
  239.          * This still works if we haven't read anything -- the dummy
  240.          * structure points to the root list, so we step through to
  241.          * the end of the root list which has a valid parent pointer.
  242.          */
  243.         for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) {
  244.             freep = p;
  245.             p = p->fts_link ? p->fts_link : p->fts_parent;
  246.             free(freep);
  247.         }
  248.         free(p);
  249.     }
  250.  
  251.     /* Free up child linked list, sort array, path buffer. */
  252.     if (sp->fts_child)
  253.         fts_lfree(sp->fts_child);
  254.     if (sp->fts_array)
  255.         free(sp->fts_array);
  256.     free(sp->fts_path);
  257.  
  258.     /* Return to original directory, save errno if necessary. */
  259.     if (!ISSET(FTS_NOCHDIR)) {
  260. #ifdef _POSIX_SOURCE
  261.         saved_errno = chdir(sp->fts_rpath) ? errno : 0;
  262.                 free(sp->fts_rpath);
  263. #else
  264.         saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
  265.         (void)close(sp->fts_rfd);
  266. #endif
  267.     }
  268.  
  269.     /* Free up the stream pointer. */
  270.     free(sp);
  271.  
  272.     /* Set errno and return. */
  273.     if (!ISSET(FTS_NOCHDIR) && saved_errno) {
  274.         errno = saved_errno;
  275.         return(-1);
  276.     }
  277.     return(0);
  278. }
  279.  
  280. /*
  281.  * Special case a root of "/" so that slashes aren't appended causing
  282.  * paths to be written as "//foo".
  283.  */
  284. #define    NAPPEND(p) \
  285.     (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
  286.         p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
  287.  
  288. FTSENT *
  289. #if __STDC__
  290. fts_read (register FTS *sp)
  291. #else
  292. fts_read(sp)
  293.     register FTS *sp;
  294. #endif
  295. {
  296.     register FTSENT *p, *tmp;
  297.     register int instr;
  298.     register char *t;
  299.  
  300.     /* If finished or unrecoverable error, return NULL. */
  301.     if (!sp->fts_cur || ISSET(FTS_STOP))
  302.         return(NULL);
  303.  
  304.     /* Set current node pointer. */
  305.     p = sp->fts_cur;
  306.  
  307.     /* Save and zero out user instructions. */
  308.     instr = p->fts_instr;
  309.     p->fts_instr = FTS_NOINSTR;
  310.  
  311.     /* If used fts_link pointer for cycle detection, restore it. */
  312.     if (sp->fts_savelink) {
  313.         p->fts_link = sp->fts_savelink;
  314.         sp->fts_savelink = NULL;
  315.     }
  316.  
  317.     /* Any type of file may be re-visited; re-stat and re-turn. */
  318.     if (instr == FTS_AGAIN) {
  319.         p->fts_info = fts_stat(sp, p, 0);
  320.         return(p);
  321.     }
  322.  
  323.     /*
  324.      * Following a symlink -- SLNONE test allows application to see
  325.      * SLNONE and recover.
  326.      */
  327.     if (instr == FTS_FOLLOW &&
  328.         (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
  329.         p->fts_info = fts_stat(sp, p, 1);
  330.         return(p);
  331.     }
  332.  
  333.     /* Directory in pre-order. */
  334.     if (p->fts_info == FTS_D) {
  335.         /* If skipped or crossed mount point, do post-order visit. */
  336.         if (instr == FTS_SKIP ||
  337.             ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev) {
  338.             if (sp->fts_child) {
  339.                 fts_lfree(sp->fts_child);
  340.                 sp->fts_child = NULL;
  341.             }
  342.             p->fts_info = FTS_DP;
  343.             return(p);
  344.         } 
  345.  
  346.         /*
  347.          * Cd to the subdirectory, reading it if haven't already.  If
  348.          * the read fails for any reason, or the directory is empty,
  349.          * the fts_info field of the current node is set by fts_build.
  350.          * If have already read and now fail to chdir, whack the list
  351.          * to make the names come out right, and set the parent state
  352.          * so the application will eventually get an error condition.
  353.          * If haven't read and fail to chdir, check to see if we're
  354.          * at the root node -- if so, we have to get back or the root
  355.          * node may be inaccessible.
  356.          */
  357.         if (sp->fts_child) {
  358.             if (CHDIR(sp, p->fts_accpath)) {
  359.                 p->fts_parent->fts_cderr = errno;
  360.                 for (p = sp->fts_child; p; p = p->fts_link)
  361.                     p->fts_accpath =
  362.                         p->fts_parent->fts_accpath;
  363.             }
  364.         } else if (!(sp->fts_child = fts_build(sp, BREAD))) {
  365.             if ISSET(FTS_STOP)
  366.                 return(NULL);
  367. #ifdef _POSIX_SOURCE
  368.             if (p->fts_level == FTS_ROOTLEVEL &&
  369.                 CHDIR(sp, sp->fts_rpath)) {
  370.                 SET(FTS_STOP);
  371.                 return(NULL);
  372.             }
  373. #else
  374.             if (p->fts_level == FTS_ROOTLEVEL &&
  375.                 FCHDIR(sp, sp->fts_rfd)) {
  376.                 SET(FTS_STOP);
  377.                 return(NULL);
  378.             }
  379. #endif
  380.             return(p);
  381.         }
  382.         p = sp->fts_child;
  383.         sp->fts_child = NULL;
  384.         goto name;
  385.     }
  386.  
  387.     /* Move to next node on this level. */
  388. next:    tmp = p;
  389.     if (p = p->fts_link) {
  390.         free(tmp);
  391.  
  392.         /* If reached the top, load the paths for the next root. */
  393.         if (p->fts_level == FTS_ROOTLEVEL) {
  394.             fts_load(sp, p);
  395.             return(sp->fts_cur = p);
  396.         }
  397.  
  398.         /* User may have called fts_set on the node. */
  399.         if (p->fts_instr == FTS_SKIP)
  400.             goto next;
  401.         if (p->fts_instr == FTS_FOLLOW) {
  402.             p->fts_info = fts_stat(sp, p, 1);
  403.             p->fts_instr = FTS_NOINSTR;
  404.         }
  405.  
  406. name:        t = sp->fts_path + NAPPEND(p->fts_parent);
  407.         *t++ = '/';
  408.         bcopy(p->fts_name, t, p->fts_namelen + 1);
  409.         return(sp->fts_cur = p);
  410.     }
  411.  
  412.     /* Move up to the parent node. */
  413.     p = tmp->fts_parent;
  414.     free(tmp);
  415.  
  416.     if (p->fts_level == FTS_ROOTPARENTLEVEL) {
  417.         /*
  418.          * Done; free everything up and set errno to 0 so the user
  419.          * can distinguish between error and EOF.
  420.          */
  421.         free(p);
  422.         errno = 0;
  423.         return(sp->fts_cur = NULL);
  424.     }
  425.  
  426.     sp->fts_path[p->fts_pathlen] = '\0';
  427.  
  428.     /*
  429.      * Cd back up to the parent directory.  If at a root node, have to cd
  430.      * back to the original place, otherwise may not be able to access the
  431.      * original node on post-order.
  432.      */
  433.     if (p->fts_level == FTS_ROOTLEVEL) {
  434. #ifdef _POSIX_SOURCE
  435.         if (CHDIR (sp, sp->fts_rpath)) {
  436. #else
  437.         if (FCHDIR(sp, sp->fts_rfd)) {
  438. #endif
  439.             SET(FTS_STOP);
  440.             return(NULL);
  441.         }
  442.     }
  443.     else if (CHDIR(sp, "..")) {
  444.         SET(FTS_STOP);
  445.         return(NULL);
  446.     }
  447.  
  448.     /* 
  449.      * If had a chdir error when trying to get into the directory, set the
  450.      * info field to reflect this, and restore errno.  The error indicator
  451.      * has to be reset to 0 so that if the user does an FTS_AGAIN, it all
  452.      * works.
  453.      */
  454.     if (p->fts_cderr) {
  455.         errno = p->fts_cderr;
  456.         p->fts_cderr = 0;
  457.         p->fts_info = FTS_ERR;
  458.     } else
  459.         p->fts_info = FTS_DP;
  460.     return(sp->fts_cur = p);
  461. }
  462.  
  463. /*
  464.  * Fts_set takes the stream as an argument although it's not used in this
  465.  * implementation; it would be necessary if anyone wanted to add global
  466.  * semantics to fts using fts_set.  An error return is allowed for similar
  467.  * reasons.
  468.  */
  469. /* ARGSUSED */
  470. int
  471. #if __STDC__
  472. fts_set (FTS *sp, FTSENT *p, int instr)
  473. #else
  474. fts_set(sp, p, instr)
  475.     FTS *sp;
  476.     FTSENT *p;
  477.     int instr;
  478. #endif
  479. {
  480. #if WIN_NT
  481.     if (sp == NULL)
  482.         ;
  483. #endif
  484.     p->fts_instr = instr;
  485.     return(0);
  486. }
  487.  
  488. FTSENT *
  489. #if __STDC__
  490. fts_children (register FTS *sp)
  491. #else
  492. fts_children(sp)
  493.     register FTS *sp;
  494. #endif
  495. {
  496.     register FTSENT *p;
  497.     int fd;
  498. #ifdef _POSIX_SOURCE /* DF_DSC */
  499.         char this_path [PATH_MAX];
  500. #endif
  501.         
  502.     /* Set current node pointer. */
  503.     p = sp->fts_cur;
  504.  
  505.     /*
  506.      * Set errno to 0 so that user can tell the difference between an
  507.      * error and a directory without entries.  If not a directory being
  508.      * visited in *pre-order*, or we've already had fatal errors, return
  509.      * immediately.
  510.      */
  511.     errno = 0;
  512.     if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR)
  513.         return(NULL);
  514.  
  515.     /* Free up any previous child list. */
  516.     if (sp->fts_child)
  517.         fts_lfree(sp->fts_child);
  518.  
  519.     /*
  520.      * If using chdir on a relative path and called BEFORE fts_read does
  521.      * its chdir to the root of a traversal, we can lose -- we need to
  522.      * chdir into the subdirectory, and we don't know where the current
  523.      * directory is, so we can't get back so that the upcoming chdir by
  524.      * fts_read will work.
  525.      */
  526.     if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
  527.         ISSET(FTS_NOCHDIR))
  528.         return(sp->fts_child = fts_build(sp, BCHILD));
  529. #ifdef _POSIX_SOURCE /* DF_DSC: Because no fchdir */
  530.         if ((getcwd(this_path, PATH_MAX)) == NULL)
  531. #else
  532.     if ((fd = open(".", O_RDONLY, 0)) < 0)
  533. #endif
  534.         return(NULL);
  535.     sp->fts_child = fts_build(sp, BCHILD);
  536. #ifdef _POSIX_SOURCE
  537.     if (chdir(this_path))
  538.         return(NULL);
  539. #else
  540.     if (fchdir(fd))
  541.         return(NULL);
  542.     (void)close(fd);
  543. #endif
  544.     return(sp->fts_child);
  545. }
  546.  
  547. /*
  548.  * This is the tricky part -- do not casually change *anything* in here.  The
  549.  * idea is to build the linked list of entries that are used by fts_children
  550.  * and fts_read.  There are lots of special cases.
  551.  *
  552.  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
  553.  * set and it's a physical walk (so that symbolic links can't be directories),
  554.  * we assume that the number of subdirectories in a node is equal to the number
  555.  * of links to the parent.  This allows stat calls to be skipped in any leaf
  556.  * directories and for any nodes after the directories in the parent node have
  557.  * been found.  This empirically cuts the stat calls by about 2/3.
  558.  */
  559. #define    ISDOT(a)    (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
  560.  
  561. static FTSENT *
  562. #if __STDC__
  563. fts_build (register FTS *sp, int type)
  564. #else
  565. fts_build(sp, type)
  566.     register FTS *sp;
  567.     int type;
  568. #endif
  569. {
  570.     register struct dirent *dp;
  571.     register FTSENT *p, *head;
  572.     register int nitems;
  573.     FTSENT *cur;
  574.     DIR *dirp;
  575.     int cderr, descend, len, level, maxlen, nlinks, saved_errno;
  576.     char *cp;
  577.  
  578.     /* Set current node pointer. */
  579.     cur = sp->fts_cur;
  580.  
  581.     /*
  582.      * Open the directory for reading.  If this fails, we're done.
  583.      * If being called from fts_read, set the fts_info field.
  584.      */
  585.     if (!(dirp = opendir(cur->fts_accpath))) {
  586.         if (type == BREAD)
  587.             cur->fts_info = FTS_DNR;
  588.         return(NULL);
  589.     }
  590.  
  591.     /*
  592.      * Nlinks is the number of possible entries of type directory in the
  593.      * directory if we're cheating on stat calls, 0 if we're not doing
  594.      * any stat calls at all, -1 if we're doing stats on everything.
  595.      */
  596.     nlinks =
  597.         ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
  598.         cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;
  599.  
  600.     /*
  601.      * If we're going to need to stat anything or we want to descend
  602.      * and stay in the directory, chdir.  If this fails we keep going.
  603.      * We won't be able to stat anything, but we can still return the
  604.      * names themselves.  Note, that since fts_read won't be able to
  605.      * chdir into the directory, it will have to return different path
  606.      * names than before, i.e. "a/b" instead of "b".  Since the node
  607.      * has already been visited in pre-order, have to wait until the
  608.      * post-order visit to return the error.  This is all fairly nasty.
  609.      * If a program needed sorted entries or stat information, they had
  610.      * better be checking FTS_NS on the returned nodes.
  611.      */
  612.     if (nlinks || type == BREAD)
  613. #ifdef _POSIX_SOURCE
  614.         if (CHDIR(sp, cur->fts_accpath)) {
  615. #else
  616.         if (FCHDIR(sp, dirfd(dirp))) {
  617. #endif
  618.             if (type == BREAD)
  619.                 cur->fts_cderr = errno;
  620.             descend = nlinks = 0;
  621.             cderr = 1;
  622.         } else {
  623.             descend = 1;
  624.             cderr = 0;
  625.         }
  626.     else
  627.         descend = 0;
  628.  
  629.         /*
  630.      * Figure out the max file name length that can be stored in the
  631.      * current path -- the inner loop allocates more path as necessary.
  632.      * We really wouldn't have to do the maxlen calculations here, we
  633.      * could do them in fts_read before returning the path, but it's a
  634.      * lot easier here since the length is part of the dirent structure.
  635.      *
  636.      * If not changing directories set a pointer so that we can just
  637.      * append each new name into the path.
  638.      */
  639.     maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
  640.     len = NAPPEND(cur);
  641.     if (ISSET(FTS_NOCHDIR)) {
  642.         cp = sp->fts_path + len;
  643.         *cp++ = '/';
  644.     }
  645.  
  646.     level = cur->fts_level + 1;
  647.  
  648.     /* Read the directory, attaching each entry to the `link' pointer. */
  649.     for (head = NULL, nitems = 0; dp = readdir(dirp);) {
  650.         if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
  651.             continue;
  652.  
  653. #ifdef _POSIX_SOURCE
  654.         if (!(p = fts_alloc(sp, dp->d_name, strlen (dp->d_name))))
  655. #else
  656.         if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)))
  657. #endif
  658.             goto mem1;
  659. #ifdef _POSIX_SOURCE
  660.         if (strlen (dp->d_name) > maxlen) {
  661. #else
  662.         if (dp->d_namlen > maxlen) {
  663. #endif
  664. #ifdef _POSIX_SOURCE
  665.             if (!fts_path(sp, strlen (dp->d_name))) {
  666. #else
  667.             if (!fts_path(sp, (int)dp->d_namlen)) {
  668. #endif
  669.                 /*
  670.                  * No more memory for path or structures.  Save
  671.                  * errno, free up the current structure and the
  672.                  * structures already allocated.
  673.                  */
  674. mem1:                saved_errno = errno;
  675.                 if (p)
  676.                     free(p);
  677.                 fts_lfree(head);
  678.                 (void)closedir(dirp);
  679.                 errno = saved_errno;
  680.                 cur->fts_info = FTS_ERR;
  681.                 SET(FTS_STOP);
  682.                 return(NULL);
  683.             }
  684.             maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
  685.         }
  686.  
  687. #ifdef _POSIX_SOURCE
  688.         p->fts_pathlen = len + strlen (dp->d_name) + 1;
  689. #else
  690.         p->fts_pathlen = len + dp->d_namlen + 1;
  691. #endif
  692.         p->fts_parent = sp->fts_cur;
  693.         p->fts_level = level;
  694.  
  695.         if (nlinks) {
  696.             /* Build a file name for fts_stat to stat. */
  697.             if (ISSET(FTS_NOCHDIR)) {
  698.                 p->fts_accpath = p->fts_path;
  699.                 bcopy(p->fts_name, cp, p->fts_namelen + 1);
  700.             } else
  701.                 p->fts_accpath = p->fts_name;
  702.             p->fts_info = fts_stat(sp, p, 0);
  703.             if (nlinks > 0 && p->fts_info == FTS_D)
  704.                 --nlinks;
  705.         } else if (cderr) {
  706.             p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS;
  707.             p->fts_accpath = cur->fts_accpath;
  708.         } else {
  709.             p->fts_accpath =
  710.                 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
  711.             p->fts_info = FTS_NSOK;
  712.         }
  713.  
  714.         p->fts_link = head;
  715.         head = p;
  716.         ++nitems;
  717.     }
  718.     (void)closedir(dirp);
  719.  
  720.     /*
  721.      * If not changing directories, reset the path back to original
  722.      * state.
  723.      */
  724.     if (ISSET(FTS_NOCHDIR)) {
  725.         if (cp - 1 > sp->fts_path)
  726.             --cp;
  727.         *cp = '\0';
  728.     }
  729.  
  730.     /*
  731.      * If descended after called from fts_children or called from
  732.      * fts_read and didn't find anything, get back.  If can't get
  733.      * back, we're done.
  734.      */
  735.     if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
  736.         cur->fts_info = FTS_ERR;
  737.         SET(FTS_STOP);
  738.         return(NULL);
  739.     }
  740.  
  741.     /* If we didn't find anything, just do the post-order visit */
  742.     if (!nitems) {
  743.         if (type == BREAD)
  744.             cur->fts_info = FTS_DP;
  745.         return(NULL);
  746.     }
  747.  
  748.     /* Sort the entries. */
  749.     if (sp->fts_compar && nitems > 1)
  750.         head = fts_sort(sp, head, nitems);
  751.     return(head);
  752. }
  753.  
  754. static u_short
  755. #if __STDC__
  756. fts_stat (FTS *sp, register FTSENT *p, int follow)
  757. #else
  758. fts_stat(sp, p, follow)
  759.     FTS *sp;
  760.     register FTSENT *p;
  761.     int follow;
  762. #endif
  763. {
  764.     int saved_errno;
  765.  
  766.     /*
  767.      * If doing a logical walk, or application requested FTS_FOLLOW, do
  768.      * a stat(2).  If that fails, check for a non-existent symlink.  If
  769.      * fail, return the errno from the stat call.
  770.      */
  771.     if (ISSET(FTS_LOGICAL) || follow) {
  772.         if (stat(p->fts_accpath, &p->fts_statb)) {
  773.             saved_errno = errno;
  774.             if (!lstat(p->fts_accpath, &p->fts_statb)) {
  775.                 errno = 0;
  776.                 return(FTS_SLNONE);
  777.             } 
  778.             errno = saved_errno;
  779.             bzero(&p->fts_statb, sizeof(struct stat));
  780.             return(FTS_NS);
  781.         }
  782.     } else if (lstat(p->fts_accpath, &p->fts_statb)) {
  783.         bzero(&p->fts_statb, sizeof(struct stat));
  784.         return(FTS_NS);
  785.     }
  786.  
  787.     /*
  788.      * Cycle detection is done as soon as we find a directory.  Detection
  789.      * is by brute force; if the tree gets deep enough or the number of
  790.      * symbolic links to directories high enough something faster might
  791.      * be worthwhile.
  792.      */
  793.     if (S_ISDIR(p->fts_statb.st_mode)) {
  794.         register FTSENT *t;
  795.         register dev_t dev;
  796.         register ino_t ino;
  797.  
  798.         dev = p->fts_statb.st_dev;
  799.         ino = p->fts_statb.st_ino;
  800.         for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL;
  801.             t = t->fts_parent)
  802.             if (ino == t->fts_statb.st_ino &&
  803.                 dev == t->fts_statb.st_dev) {
  804.                 sp->fts_savelink = p->fts_link;
  805.                 p->fts_link = t;
  806.                 return(FTS_DC);
  807.             }
  808.         return(FTS_D);
  809.     }
  810.  
  811. #ifndef _POSIX_SOURCE
  812.         if (S_ISLNK(p->fts_statb.st_mode))
  813.             return(FTS_SL);
  814. #endif
  815.     if (S_ISREG(p->fts_statb.st_mode))
  816.         return(FTS_F);
  817.     return(FTS_DEFAULT);
  818. }
  819.  
  820. #define    R(type, nelem, ptr) \
  821.     (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
  822.  
  823. static FTSENT *
  824. #if __STDC__
  825. fts_sort (FTS *sp, FTSENT *head, register int nitems)
  826. #else
  827. fts_sort(sp, head, nitems)
  828.     FTS *sp;
  829.     FTSENT *head;
  830.     register int nitems;
  831. #endif
  832. {
  833.     register FTSENT **ap, *p;
  834.  
  835.     /*
  836.      * Construct an array of pointers to the structures and call qsort(3).
  837.      * Reassemble the array in the order returned by qsort.  If unable to
  838.      * sort for memory reasons, return the directory entries in their
  839.      * current order.  Allocate enough space for the current needs plus
  840.      * 40 so we don't realloc one entry at a time.
  841.      */
  842.     if (nitems > sp->fts_nitems) {
  843.         sp->fts_nitems = nitems + 40;
  844.         if (!(sp->fts_array =
  845.             R(FTSENT *, sp->fts_nitems, sp->fts_array))) {
  846.             sp->fts_nitems = 0;
  847.             return(head);
  848.         }
  849.     }
  850.     for (ap = sp->fts_array, p = head; p; p = p->fts_link)
  851.         *ap++ = p;
  852.     qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
  853.     for (head = *(ap = sp->fts_array); --nitems; ++ap)
  854.         ap[0]->fts_link = ap[1];
  855.     ap[0]->fts_link = NULL;
  856.     return(head);
  857. }
  858.  
  859. static FTSENT *
  860. #if __STDC__
  861. fts_alloc (FTS *sp, char *name, register int len)
  862. #else
  863. fts_alloc(sp, name, len)
  864.     FTS *sp;
  865.     char *name;
  866.     register int len;
  867. #endif
  868. {
  869.     register FTSENT *p;
  870.  
  871.     /*
  872.      * Variable sized structures; the name is the last element so
  873.      * we allocate enough extra space after the structure to store
  874.      * it.
  875.      */
  876.     if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
  877.         return(NULL);
  878.     bcopy(name, p->fts_name, len + 1);
  879.     p->fts_namelen = len;
  880.     p->fts_path = sp->fts_path;
  881.     p->fts_instr = FTS_NOINSTR;
  882.     p->fts_cderr = 0;
  883.     p->fts_number = 0;
  884.     p->fts_pointer = NULL;
  885.     return(p);
  886. }
  887.  
  888. static void
  889. #if __STDC__
  890. fts_lfree (register FTSENT *head)
  891. #else
  892. fts_lfree(head)
  893.     register FTSENT *head;
  894. #endif
  895. {
  896.     register FTSENT *p;
  897.  
  898.     /* Free a linked list of structures. */
  899.     while (p = head) {
  900.         head = head->fts_link;
  901.         free(p);
  902.     }
  903. }
  904.  
  905. /*
  906.  * Allow essentially unlimited paths; certain programs (find, rm, ls) need to
  907.  * work on any tree.  Most systems will allow creation of paths much longer
  908.  * than MAXPATHLEN, even though the kernel won't resolve them.  Add an extra
  909.  * 128 bytes to the requested size so that we don't realloc the path 2 bytes
  910.  * at a time.
  911.  */
  912. static char *
  913. #if __STDC__
  914. fts_path (FTS *sp, int size)
  915. #else
  916. fts_path(sp, size)
  917.     FTS *sp;
  918.     int size;
  919. #endif
  920. {
  921.     sp->fts_pathlen += size + 128;
  922.     return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path));
  923. }
  924.